package Array_and_String;

/*
寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/c3ki5/
 */

import java.util.Arrays;

public class _54寻找旋转排序数组中的最小值 {
    public static void main(String[] args) {

        int[] n = {4,5,1,2,3};

        System.out.println(findMin2(n));

    }

    public static int findMin(int[] nums) {

        int left = 0, right = nums.length - 1;
        int min = nums[left];
        while (left < right) {
            int mid = left + right >> 1;
            int midnum = nums[mid],prenum,aftnum;
            if(mid - 1 >= 0){
                prenum = nums[mid - 1];
            }else {
                prenum = nums[0];
            }
            if(mid + 1 < nums.length){
                aftnum = nums[mid + 1];
            }else {
                aftnum = nums[nums.length - 1];
            }


            if (prenum <= midnum && aftnum <= midnum) {
                return nums[mid +1];
            }
            if (prenum >= midnum && aftnum >= midnum) {
                return nums[mid];
            }

            if(prenum <= midnum && midnum <= aftnum && aftnum >= min) {
                    left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return min;
    }

    //官解
    //官解的图非常好理解！！
    //链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/698479/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-5irwp/
    //第一种情况是 nums[pivot]<nums[high]。如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。
    //第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。
    //由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。
    //因此不会存在 nums[pivot]=nums[high] 的情况。
    //当二分查找结束时，我们就得到了最小值所在的位置。

    public static int findMin2(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else if (nums[pivot] > nums[high]) {
                low = pivot + 1;
            }else {
                return nums[pivot];
            }
        }
        return nums[low];
    }

    //画图可以节省一大堆思考时间，可以很清楚明白的看出一些规律
    //发现了mid两种取法,而采用mid = left + (right - left) / 2 的原因
    //原因就是mid = (left + right) / 2 容易溢出！
    //因为left+right很容易超过int范围！
    //而mid = left + (right - left) / 2 不容易溢出
    //所以建议以后写二分时要用mid = left + (right - left) / 2

}
